package main

import (
	"fmt"
	"math/rand"
	"time"
)

func countingSort(arr []int) []int {
	length := len(arr)
	maxValue := arr[0]
	for i := 0; i < length; i++ {
		if maxValue < arr[i] {
			maxValue = arr[i]
		}
	}
	bucket := make([]int, maxValue+1)

	for i := 0; i < length; i++ {
		bucket[arr[i]]++
	}

	key := 0
	for j := 0; j < maxValue+1; j++ {
		for bucket[j] > 0 {
			arr[key] = j
			key++
			bucket[j]--
		}
	}
	return arr
}
func main() {
	arr := make([]int, 100)
	rand.Seed(time.Now().UnixNano())
	length := len(arr)
	for i := 0; i < length; i++ {
		arr[i] = rand.Intn(1000)
	}
	fmt.Println(arr)
	fmt.Println(countingSort(arr))
}
